<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 打家劫舍III题：
         * 输入：nums = [3,2,3,null,3,null,1]
         * 输出：7
         * 解释：小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
         * 
         * 输入: root = [3,4,5,1,3,null,1]
         * 输出: 9
         * 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
         * 思路：区别：首位连接成环，首尾不能同时去打劫
         * 
        */
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        let a = new TreeNode(3)
        let b = new TreeNode(2)
        let c = new TreeNode(3)
        let d = new TreeNode(null)
        let e = new TreeNode(3)
        let f = new TreeNode(null)
        let g = new TreeNode(1)
        a.left = b
        a.right = c
        b.left = d
        b.right = e
        c.left = f
        c.right = g
        /* 
            时间：O(n) 每个节点只遍历了一次，就是O(n)；取决于递归的深度（树的层级） 和 每次递归的操作次数
            空间：O(logn) 如果是平衡二叉树，就是logn,否则可能是n，一个节点一个层级；平衡二叉树，每个节点左右子树的高度差不大于1,
        */
        var rob = function(root) {
            function postorderTraversal (node) {
                // 如果节点为空，返回null
                if (!node) return [0, 0]
                // 遍历左子树
                const left = postorderTraversal(node && node.left)
                // 遍历右子树
                const right = postorderTraversal(node && node.right)
                // 不偷当前节点，左右子节点都可以，偷或者不偷，取最大值
                let notSteal = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
                // 偷当前节点，左右子节点只能不偷，
                let steal = node.val + left[0] + right[0]
                // 返回偷和不偷
                return [notSteal, steal]
            }
            const res = postorderTraversal(root)
            return Math.max(...res)
        };
        console.log(rob(a));
    </script>
</body>

</html>